This disclosure relates generally to the field of manufacture semiconductor integrated circuits using triple-pattern lithography (TPL), and more particularly to methods, systems, and computer program products validating triple-pattern lithography layout decomposition.
In semiconductor fabrication processes, the resolution of a photoresist pattern begins to blur at about 45 nanometers (nm) half pitch. In order to provide semiconductor layers with smaller distances between adjacent patterns, without resorting to such expedients as extreme ultra violet (EUV) technology, double-patterning has been developed. In double-patterning, the layout of a single layer of an integrated circuit (IC) is decomposed into two masks (alternatively referred to as “photomasks”). In double-patterning, there are two separate exposure and etching steps using each of the two masks separately. The advantages achieved with double-patterning have been extending using triple-patterning, wherein the layout is decomposed into three separate masks.
In multiple-patterning, such as double-patterning and triple-patterning, design rules provide that polygons of the layout (of the same device layer) that are separated from each other by less than a predetermined distance are not to be in the same mask. Graph theory has been applied to the analysis and validation of multiple-pattern decompositions. A given device layout can be represented as a conflict graph CG=(V, E), wherein each vertex V represents a polygon (i.e., a circuit pattern) of the layout and an edge E is formed connecting two vertices, when the distance between two corresponding polygons is less than a minimum separation distance for clearly exposed patterns using a single photomask. In graph theory, the vertices are also referred to more generally as nodes and the edges are alternatively referred to as links. A loop is the loop created by the edges connecting the vertices. A closed loop in a conflict graph with an even number of vertices can be decomposed into two masks. Accordingly, a decomposition violation in double-patterning can be detected by the presence of a loop with an odd number of vertices in the conflict graph. However, decomposition validation in triple-patterning is a much more complex problem. In fact, the problem is NP-complete, which makes the problem not solvable in a reasonable amount of time.